package mo.leetcode_top;

import java.util.*;
import java.util.stream.Collectors;

public class L17 {

    private static Map<Integer, List<Character>> num2char = new HashMap<>();
    static {
        num2char.put(2, Arrays.asList('a', 'b', 'c'));
        num2char.put(3, Arrays.asList('d', 'e', 'f'));
        num2char.put(4, Arrays.asList('g', 'h', 'i'));
        num2char.put(5, Arrays.asList('j', 'k', 'l'));
        num2char.put(6, Arrays.asList('m', 'n', 'o'));
        num2char.put(7, Arrays.asList('p', 'q', 'r', 's'));
        num2char.put(8, Arrays.asList('t', 'u', 'v'));
        num2char.put(9, Arrays.asList('w', 'x', 'y', 'z'));
    }



    public List<String> letterCombinations(String digits) {
        List<StringBuilder> res = new ArrayList<>();
        for (int i = 0; i < digits.length(); i++) {
            int num = digits.charAt(i) - '0';
            List<Character> chars = num2char.get(num);
            if (res.size() == 0) {
                for (int j = 0; j < chars.size(); j++) {
                    StringBuilder builder = new StringBuilder();
                    builder.append(chars.get(j));
                    res.add(builder);
                }
            } else {
                List<StringBuilder> added = new ArrayList<>();
                for (int j = 0; j < chars.size(); j++) {
                    for (int k = 0; k < res.size(); k++) {
                        StringBuilder newBuilder = new StringBuilder(res.get(k)).append(chars.get(j));
                        added.add(newBuilder);
                    }
                }
                res = added;
            }
        }

        return res.stream().map(StringBuilder::toString).collect(Collectors.toList());
    }


    //class Solution {
    //    List<String> result = new ArrayList<>();
    //    public List<String> letterCombinations(String digits) {
    //        if(digits.length() == 0) {
    //            return result;
    //        }
    //        Map<Character,String> map = new HashMap<>();
    //        map.put('2',"abc");
    //        map.put('3',"def");
    //        map.put('4',"ghi");
    //        map.put('5',"jkl");
    //        map.put('6',"mno");
    //        map.put('7',"pqrs");
    //        map.put('8',"tuv");
    //        map.put('9',"wxyz");
    //        dfs(digits, map, 0, new StringBuilder());
    //        return result;
    //    }
    //    private void dfs(String digits, Map<Character,String> map, int index, StringBuilder sb) {
    //        if(index == digits.length()) {
    //            result.add(sb.toString());
    //            return;
    //        }
    //        Character ch = digits.charAt(index);
    //        String str = map.get(ch);
    //        for(int i = 0; i < str.length(); i++) {
    //            sb.append(str.charAt(i));
    //            dfs(digits, map, index + 1, sb);
    //            sb.deleteCharAt(sb.length() - 1);
    //        }
    //    }
    //}

    List<String> result = new ArrayList<>();
    public List<String> letterCombinations2(String digits) {
        if(digits.length() == 0) {
            return result;
        }
        Map<Character,String> map = new HashMap<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        dfs(digits, map, 0, new StringBuilder());
        return result;
    }
    private void dfs(String digits, Map<Character,String> map, int index, StringBuilder sb) {
        if(index == digits.length()) {
            result.add(sb.toString());
            return;
        }
        Character ch = digits.charAt(index);
        String str = map.get(ch);
        for(int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            dfs(digits, map, index + 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) {
        L17 test = new L17();
        System.out.println(test.letterCombinations2("23"));
    }
}
